package test.n00100;


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Problem00170 {
    public static void main(String[] args) {
        println("23");
        println("");
        println("2");
    }

    public static void println(String digits) {
        Solution ss = new Solution();
        System.out.println(digits + "," + ss.letterCombinations(digits));
    }

    public static class Solution {

        /**
         * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
         * <p>
         * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
         * <p>
         * 来源：力扣（LeetCode）
         * 链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number
         * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
         * <p>
         * 提示：
         * <p>
         * 0 <= digits.length <= 4
         * digits[i] 是范围 ['2', '9'] 的一个数字。
         *
         * @param digits
         * @return
         */
        public List<String> letterCombinations(String digits) {
            if (digits.length() == 0) {
                return Collections.emptyList();
            }
            List<String> list = new ArrayList<>();
            backtrack(list, digits, 0, new StringBuffer());
            return list;
        }

        public void backtrack(List<String> combinations, String digits, int index, StringBuffer combination) {
            if (digits.length() == index) {
                combinations.add(combination.toString());
            } else {
                char digit = digits.charAt(index);
                String letters = matrix[digit - '1'];
                int lettersCount = letters.length();
                for (int i = 0; i < lettersCount; i++) {
                    combination.append(letters.charAt(i));
                    backtrack(combinations, digits, index + 1, combination);
                    combination.deleteCharAt(index);
                }
            }
        }

        String[] matrix = {
                "",
                "abc",
                "def",
                "ghi",
                "jkl",
                "mno",
                "pqrs",
                "tuv",
                "wxyz",
        };
    }
}
